package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;
import sun.launcher.resources.launcher;

import util.LogUtils;

/*
 * 
原题
	　Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. 
　　push(x) – Push element x onto stack. 
　　pop() – Removes the element on top of the stack. 
　　top() – Get the top element. 
　　getMin() – Retrieve the minimum element in the stack. 
题目大意	
	设计一个栈，支持push，pop，top，和查找最小的元素操作（常量时间） 
	MinStack minStack = new MinStack();
	minStack.push(-2);
	minStack.push(0);
	minStack.push(-3);
	minStack.getMin();   --> Returns -3.
	minStack.pop();
	minStack.top();      --> Returns 0.
	minStack.getMin();   --> Returns -2.
解题思路
	别想太多~~
　	栈：头插法, 
	最小值：用个属性top来保存
 * @Date 2017-10-01 16：34
 */
public class _155_Min_Stack {
	/**
	 * 以链表的方式实现
	 * @author Administrator
	 *
	 */
	private class Node {
		int  val;
		int  min;
		Node next;
		public Node(int val) {this.val = val;}
	}
	
	private Node top;
	
    /** initialize your data structure here. */
    public _155_Min_Stack() {
        
    }
    
    public void push(int x) {
    	if (top == null) {
    		top = new Node(x);
    		top.min = x;
    	} else {
    		Node temp = new Node(x);
    		temp.next = top;
    		top = temp;
    		top.min = Math.min(top.next.min, x);		//min保存的当时插入时整个链表的最小值
    	}
    }
    
    public void pop() {
    	top = top.next;
    	return;
    }
    
    public int top() {
    	return top==null ? -1 : top.val;
    }
    
    public int getMin() {
        return top==null ? -1 : top.min;
    }
    
	public static void main(String[] args) {
		_155_Min_Stack obj = new _155_Min_Stack();
	
	}

}
